# coding: utf-8
from itertools import product


class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        print(n)
        if n == 0:
            return ['']
        if n == 1:
            return ['()']
        # i is how many parent is out side 1.
        res = ['(' + p + ')' for p in self.generateParenthesis(n-1)]
        # res = []
        for i in range(0, n-1):
            # print(i)
            # print(n-1-i)
            pre = self.generateParenthesis(i)
            inner = self.generateParenthesis(n-1-i)
            res += [p + '(' + i + ')' for p, i in product(pre, inner)]
            res += [i + '(' + p + ')' for p, i in product(pre, inner)]
        return list(set(res))


if __name__ == '__main__':
    print(Solution().generateParenthesis(3))